# We can have 200 with:
# * 1 coin of 200 (1 possibility)
# * 0 coin of 200 +
#   * 2 coin of 100 (1 possibility)
#   * 1 coin of 100
#     * ... all possibility of doing 100 with coin <= 50 (x possibility)
#   * 0 coin of 100
#     * ... all possibility of doing 200 with coin <= 50 (x possibility)
#
# We use recursive function f(c, s)
# * compute all possibility to go to sum d < s with coin c
# * Add all possibility for all f(smaller coin, s - d)

import lib.memoize

coin = [200, 100, 50, 20, 10, 5, 2, 1]

@lib.memoize.LruCache
def f(c, s):
    """ Possibility number for summing s with coin >= coin[c] """

    # Case where all coin except 1 was handled
    if coin[c] == 1:
        return 1

    # Handle all possibility for coin c
    res = 0
    for d in xrange(0, s+1, coin[c]):
        res += f(c + 1, s - d)
    return res

def Solve():
    result = f(0, 200)
    return result

